import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

class LRUCache {
    private int capacity;
    private List<Integer> LRUList;
    private HashMap<Integer, Integer> LRUMap;

    public LRUCache(int capacity) {
        LRUList = new ArrayList<Integer>();
        LRUMap = new HashMap<Integer, Integer>();
        this.capacity = capacity;
    }

    public int get(int key) {
        Integer result = LRUMap.get(key);
        if (null == LRUMap.get(key)) {
            return -1;
        } else {
            LRUList.remove((Object)key);
            LRUList.add(0, key);
            return result;
        }
    }

    public void put(int key, int value) {
        if (null == LRUMap.get(key)) {
            if(LRUList.size()>=capacity){
                Integer remove = LRUList.remove(capacity-1);
                LRUMap.remove(remove);
            }
            LRUList.add(0,key);
            LRUMap.put(key,value);
        }else{
            LRUMap.put(key,value);
        }
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */